package com.example.demo.leetcode;

/**
 * 链接：<a href="https://leetcode.cn/problems/buy-two-chocolates/description/?envType=daily-question&envId=2024-01-26">https://leetcode.cn/problems/buy-two-chocolates/description/?envType=daily-question&envId=2024-01-26</a>
 * <p>
 * 给你一个整数数组 prices ，它表示一个商店里若干巧克力的价格。同时给你一个整数 money ，表示你一开始拥有的钱数。
 * <p>
 * 你必须购买 恰好 两块巧克力，而且剩余的钱数必须是 非负数 。同时你想最小化购买两块巧克力的总花费。
 * <p>
 * 请你返回在购买两块巧克力后，最多能剩下多少钱。如果购买任意两块巧克力都超过了你拥有的钱，请你返回 money 。注意剩余钱数必须是非负数。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：prices = [1,2,2], money = 3 <br>
 * 输出：0 <br>
 * 解释：分别购买价格为 1 和 2 的巧克力。你剩下 3 - 3 = 0 块钱。所以我们返回 0 。<br>
 * <p>
 * <p>
 * 示例 2： <br>
 * <p>
 * 输入：prices = [3,2,3], money = 3 <br>
 * 输出：3 <br>
 * 解释：购买任意 2 块巧克力都会超过你拥有的钱数，所以我们返回 3 。 <br>
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/01/26 10:26
 */
public class _2706_购买两块巧克力 {


    public static void main(String[] args) {
        int[] prices = {3, 2, 3};
        int money = 3;
        int i = new Solution().buyChoco(prices, money);
        System.out.println(i);
    }

    public static class Solution {
        public int buyChoco(int[] prices, int money) {
            //选择排序
//            selectSort(prices);

            //快速排序
//            quickSort(prices, 0, prices.length - 1);

            //冒泡排序
            bubbleSort(prices);

            int first = prices[0];
            int second = prices[1];
            if (money >= (first + second)) {
                return money - first - second;
            }
            return money;
        }

        /**
         * 选择排序,选择排序最外层只需要2次即可。
         * 时间复杂度为O(2*n)
         * 空间复杂度为O(1)
         */
        private void selectSort(int[] prices) {
            for (int i = 0; i < 2; i++) {
                for (int j = i + 1; j < prices.length; j++) {
                    if (prices[i] > prices[j]) {
                        int temp = prices[i];
                        prices[i] = prices[j];
                        prices[j] = temp;
                    }
                }
            }
        }


        /**
         * 快速排序
         * 时间复杂度O(nlogn)
         * 空间复杂度O(1)
         *
         * @param prices
         * @param left
         * @param right
         */
        private void quickSort(int[] prices, int left, int right) {
            if (left < right) {
                int partion = partion(prices, left, right);
                quickSort(prices, left, partion - 1);
                quickSort(prices, partion + 1, right);
            }
        }

        private int partion(int[] prices, int left, int right) {
            int pivot = prices[left];
            while (left < right) {
                while (left < right && prices[right] >= pivot) {
                    right--;
                }
                prices[left] = prices[right];

                while (left < right && prices[left] <= pivot) {
                    left++;
                }
                prices[right] = prices[left];
            }
            prices[left] = pivot;
            return left;
        }


        /**
         * 冒泡排序
         * 时间复杂度O(n^2)
         * 空间复杂度O(1)
         *
         * @param
         * @return
         * @author WangYX
         * @date 2024/01/26 11:10
         */
        private void bubbleSort(int[] prices) {
            for (int i = 0; i < prices.length; i++) {
                for (int j = 0; j < prices.length - i - 1; j++) {
                    if (prices[j] > prices[j + 1]) {
                        int temp = prices[j + 1];
                        prices[j + 1] = prices[j];
                        prices[j] = temp;
                    }
                }
            }
        }
    }

}
